package edu.uci.ics.ai.maze.models;

import edu.uci.ics.ai.maze.utils.Constants;
import edu.uci.ics.ai.maze.utils.MazeUtils;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Maze implements Cloneable {

  public static final Vertex ORIGIN = new Vertex(0, 0);
  private static final Vertex NEGATIVE_TEST_POINT = new Vertex(-1, -1);
  
  private final Vertex start;
  private final Vertex goal;
  private final List<Vertex> vertices;
  private final List<Polygon> obstacles;
  private final Map<Edge, Boolean> visibleCache;
  private final int maxX;
  private final int maxY;
  private final String name;

  public Maze(Vertex start, Vertex goal, List<Polygon> obstacles) {
    this(start, goal, obstacles, null);
  }

  public Maze(Vertex start, Vertex goal, List<Polygon> obstacles, String name) {
    this.start = start;
    this.goal = goal;
    this.obstacles = Collections.unmodifiableList(obstacles);
    
    List<Vertex> temp = new ArrayList<Vertex>();
    for (Polygon p : obstacles) {
      for (Vertex v : p.getVertices()) {
        temp.add(v);
      }
    }
    this.vertices = Collections.unmodifiableList(temp);
    this.visibleCache = new HashMap<Edge, Boolean>();

    int tempMaxX = 0;
    int tempMaxY = 0;
    for (Vertex v : this.vertices) {
      tempMaxX = Math.max(tempMaxX, v.getX());
      tempMaxY = Math.max(tempMaxY, v.getY());
    }
    this.maxX = tempMaxX;
    this.maxY = tempMaxY;

    this.name = name;
  }

  public Vertex getStart() {
    return start;
  }

  public Vertex getGoal() {
    return goal;
  }

  /**
   * Returns the list of all the vertices of all the Polygons in the Maze.
   *
   * @return the vertices of all the polygons in the Maze
   */
  public List<Vertex> getVertices() {
    return Collections.unmodifiableList(vertices);
  }

  /**
   * Returns the list of Polygons in the Maze.
   *
   * @return polygons in the Maze
   */
  public List<Polygon> getPolygons() {
    return Collections.unmodifiableList(obstacles);
  }

  /**
   * Returns true if the {@code end} is visible from the {@code start};
   * otherwise returns false.
   *
   * @param start the start point
   * @param end the end point
   * @return true, if visible; otherwise, false
   */
  public boolean isVisible(final Vertex start, final Vertex end) {
    boolean visible;
    Edge e = new Edge(start, end);
    if (getVisibleCache().containsKey(e)) {
      visible = getVisibleCache().get(e);
    } else {
      Edge reverse = e.getReverse();
      if (getVisibleCache().containsKey(reverse)) {
        visible = getVisibleCache().get(reverse);
      } else {
        visible = checkVisibility(start, end);
        getVisibleCache().put(e, visible);
      }
    }
    return visible;
  }

  /**
   * @return the visibleCache
   */
  protected Map<Edge, Boolean> getVisibleCache() {
    return visibleCache;
  }

  public void clearCache() {
    visibleCache.clear();
  }

  /**
   * Returns the maximum x-coordinate in the Maze.
   *
   * @return the maxX
   */
  public int getMaxX() {
    return maxX;
  }

  /**
   * Returns the maximum y-coordinate in the Maze.
   *
   * @return the maxY
   */
  public int getMaxY() {
    return maxY;
  }

   /**
   * Returns true if there is a straight line path between start and end;
   * otherwise, returns false.
   *
   * @param start the start point
   * @param end the end point
   * @param obstacles the polygon obstacles in the maze
   * @return true if there is a straight line path between start and end
   */
  protected boolean checkVisibility(Vertex start, Vertex end) {
    //cannot be null or negative
    if (start == null || end == null
            || start.getX() < 0 || start.getY() < 0
            || end.getX() < 0 || end.getY() < 0) {
      return false;
    }

    //cannot see itself
    if (start.equals(end)) {
      return false;
    }

    Edge curLine = new Edge(start, end);  //construct the line of sight


    // make sure polygons are set on the vertices
    if (start.getPolygon() == null) {
      start.setPolygon(findPolygon(start));
    }

    if (end.getPolygon() == null) {
      end.setPolygon(findPolygon(end));
    }


    // if two points are from the same polygon
    if (end.getPolygon() != null && end.getPolygon() == start.getPolygon()) {
      //outside check first
      if (!outsideCheck(curLine)) {
        return false;
      }
      return insideCheck(curLine, start.getPolygon());
    } else {
      return outsideCheck(curLine);
    }
  }

  protected Polygon findPolygon(Vertex v) {
    int i = 0;
    for (Polygon p : obstacles) {
      i++;
      for (Edge e : p.getEdges()) {
        if (e.isIntersecting(v)) {
          v.setPolygon(e.getStart().getPolygon());
          return v.getPolygon();//i + 1;
        }
      }
    }
    return null;
  }

  protected boolean outsideCheck(Edge curLine) {
    //for each edge in the maze,
    for (Polygon polygon : obstacles) {
      for (Edge e : polygon.getEdges()) { //search through the edges list
        if (curLine.isIntersecting(e, 0)) {//if any of them cross the line of
          //allow points on the line
          if (!e.isIntersecting(curLine.getStart()) && !e.isIntersecting(curLine.getEnd())) {
            return false;		//cite we have invisible case.
          }
        }
      }
    }
    return true;
  }

  protected static boolean insideCheck(final Edge curLine, final Polygon polygon) {
    Edge tmpLine = curLine.enlarge(Constants.enlarge);
    Edge checkLine = new Edge(NEGATIVE_TEST_POINT, tmpLine.getMidPoint());
    int numbersOfCut_firstTime = 0;
    int numbersOfCut_secondTime = 0;
    int numbersOfCut_thirdTime = 0;

    for (Edge e : polygon.getEdges()) {
      e = e.enlarge(Constants.enlarge);
      if (tmpLine.equals(e) || tmpLine.equals(e.getReverse())) {
        return true;
      }

      // Do 3 checks with first time skewed the line to the left at origin,
      // second time with no skew and third time with the line skewed to the
      // right at origin. If one of them results in different value, pick the
      // other two values.
      if (checkLine.isIntersecting(e, 0)) {
        numbersOfCut_firstTime++;
      }
      if (checkLine.isIntersecting(e, -1)) {
        numbersOfCut_secondTime++;
      }
      if (checkLine.isIntersecting(e, 1)) {
        numbersOfCut_thirdTime++;
      }
    }
    numbersOfCut_firstTime = (numbersOfCut_firstTime % 2 == 0 ? 1 : 0);
    numbersOfCut_secondTime = (numbersOfCut_secondTime % 2 == 0 ? 1 : 0);
    numbersOfCut_thirdTime = (numbersOfCut_thirdTime % 2 == 0 ? 1 : 0);
    if (numbersOfCut_firstTime == numbersOfCut_secondTime
            || numbersOfCut_firstTime == numbersOfCut_thirdTime) {
      return numbersOfCut_firstTime == 1;
    }
    return numbersOfCut_secondTime == 1;
  }
}
